1. Technical Field
The presently disclosed embodiments are directed to methods and systems for improving the performance of digital color printers. More specifically, color combinations seen during several job runs on a digital color printer are recorded and that information is used to pre-calculate blocks of halftone tiles ahead of time for faster performance.
2. Description of Related Art
When an image is prepared for rendering on an electronic device the image is represented as a set of pixels, or a two dimensional path describing an area to be marked. Each pixel describes a small portion of the image in terms of colorant pixel values for the colorants available on the rendering device. A path describes a shape in two dimensions, for example a letter from a font, a line of some thickness, or a rectangle. For example, typically a cathode ray tube (CRT) based computer display screen is comprised of red (R), green (G) and blue (B) phosphors. An image prepared for display on a CRT is described with a set of pixels. Each pixel describes the intensity with which the red, green and blue phosphors are to be illuminated on a small portion of the CRT.
A similar procedure is followed when an image is prepared for rendering on a printing device. Currently, at least some color printing devices apply cyan (C), magenta (M), yellow (Y), and sometimes black (K) colorants to a print medium, such as paper or velum, in order to render an image. Such printing devices are said to operate in a CMY or CMYK color space. When an image is prepared for rendering on a color-printing device, the image is represented as a set of pixels. Each pixel describes a small portion of the image by calling for an appropriate mixture of the available colorants. Typically, the pixel value for each colorant can range from 0 to 255. However, since many color-printing devices can either only place a dot or not place a dot in a particular point on the page, the pixel values must be reduced in bit depth to binary, that is, each pixel represents either a 0 or a 1.
Where color matching is required between two devices such as the CRT operating in RGB space and the printer operating in CMYK space, transforms based on calibration and measurement are required. In such a situation it is possible, for example, that the pure red RGB CRT pixel mentioned above, is mapped to a CMYK printer pixel calling for a less than fully saturated magenta component and a small amount of a cyan component. Furthermore, if one wants to print a copy of the original pure red RGB CRT pixel on a second printer it is quite likely that a second transform will have to be used. That transform may translate the original RGB CRT pixel to a second CMYK pixel. One reason two different CMYK printers may require different transforms is that different printers use different colorants. Each of the C, M, Y, and K images in a CMYK printer are called separations. For example, we can refer to the C separation in isolation of the other M, Y, and K separations if need be.
Print job attributes can also affect color transformations. For example, the mark resolution attribute provides the number of dots or pixels a printer can print in a given unit of length, such as an inch. Mark resolution is also typically given for the vertical and horizontal dimensions of a page. Another attribute that can affect color transformation is print quality mode. The print quality mode typically refers to different methods of transformation, yielding a different perceptual quality for the user. For example, one might prefer a ‘punchy’ output to a more perceptually accurate output. Print quality mode can also be low, medium, and high, for example. In this case a tradeoff is being made that the customer can control. For example, high quality may take longer to print and use more colorant material.
From the foregoing discussion it can be seen that an image prepared for rendering on a first device may need to be transformed if it is to be properly rendered on a second device. Such a transformation is an attempt to emulate the first or source device onto the second or destination device.
An image processor must be able to satisfactorily transform images, prepared for rendering on a staggeringly large number of source devices, for rendering on an equally large number of rendering devices. For example, a personal computer configured to operate as an image processor, through the use of, for example, a web browser, word processor, or desktop publishing software, must be able to accept images created or downloaded from almost anywhere, and render the images pleasingly on any image output terminal the user connects to the personal computer. For example, the image processor must be able to pleasingly display images on a computer screen and send commands to have images rendered pleasingly on any printer the user connects to the personal computer.
Similarly, document processors, printers, and copiers must transform images pleasingly and accurately. In digital printing, a customer or submitted job is converted into a printable job via a Raster Image Processor (RIP). This process converts customer jobs, represented in a Page Description Language, to complete images that are used to drive the color-printing device to mark the paper. An example of a Page Description Language is PostScript. Using this language, text is represented by an operator in the language called ‘show’, lines are represented using the ‘stroke’ operator, and rectangles and polygons are represented using the ‘fill’ operator. PostScript can also represent sampled images using variations of the ‘image’ operator.
One of the functions contained in the RIP is the conversion from the color space defined within the customer job to that of the color space of the printing device. The color accuracy requirements for digital printing can be very stringent. For example, in a large print job, comprising a corporate sales presentation, it is very important that colors in a company logo be reproduced accurately and consistently. Similarly, colors in a clothing catalog must match the colors on depicted garments.
Typically color transformations are carried out using look up tables. For example, an image prepared for rendering in a RGB color space of a computer monitor, is transformed into a CMYK color space of a printer, using a three-dimensional look up table. Each of the RGB parameters is used as an axis or index into the look up table. The RGB parameters are typically represented by 8-bit values for each of the R, G, and B components. Such a 24-bit RGB vector is capable of addressing over 16.77 million locations or describing over 16.77 million colors.
A further step in the RIP process converts the continuous tone (for example 8 bits per pixel) CMYK data to binary or lower bits per pixel (for example 1 bit per pixel) in order for the color-printing device to place colorant on the paper. This step in the RIP process is called halftoning. Halftoning either applies to input images in the source representation of the document (for example ‘image’ in PostScript Page description language) as well as other marking operators that are described as text, lines, or fills.
When halftoning CMYK data input as text, lines, or fills, the halftoning process covers the area to be marked with predefined patterns of 1s and 0s that represent the halftone screen. Usually, there is what is called halftone machinery, which performs the halftoning operations. The halftoning operations of the halftoning machinery perform two basic functions: image halftoning, and tile creation. Tile creation is the process of generating a rectangular image of 1s and 0s that represent the halftone at a particular color level. These tiles are then used to fill the areas to be marked by the text, line, or fill operations in the RIP.
There are two forms of halftone tile creation depending on the needs of the color-printing device. The simple form is called scalar halftoning, which treats each of the C, M, Y, and K separations independently. The more complex form is called vector halftoning, which treats the C, M, Y, and K separations as a vector of four colorants (C,M,Y,K) as a single unit. In both cases, halftone tiles are created to use in marking areas of text, lines, and fills. In the scalar case (assuming 8 bits per pixel data), each of the C, M, Y, and K color separations has 256 values. Each value has a corresponding halftone tile. When taken independently, there are 256 times four, or 1024, unique halftone tiles that must be created for scalar halftoning. In the vector halftoning case, because the CMYK separations are not independent, each combination of all colors has a unique halftone tile. In this case there are 2564=4,294,967,296 unique halftone tiles that must be created for vector halftoning.
An example halftone tile size is 128 by 128 pixels. Each tile consumes 2 kilobytes of memory. For scalar halftoning, the memory required to create and store 1024 tiles is 2 megabytes. For vector halftoning, the memory required to store all halftone tiles is 8,796,093,022,208 bytes, or roughly 8 terabytes. Modern computing devices can not store this many combinations. Because it takes time to create halftone tiles, ordinarily they are created and stored. In order to store frequently required halftone tiles, caching schemes are used. Caching tiles is the process of saving pre-computed tiles in an efficient data structure such that they are quickly retrieved when needed. One such efficient data structure that is commonly used is a hash table. A hash table takes as input a number, and uses it to look into a table for the corresponding value for the number. A hash table can be used to very efficiently find halftone tiles without having to store all the halftone tiles. Hash tables can store a small subset of commonly used tiles to significantly speed up the halftoning process.